package com.myown.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 排序算法<p>
 *
 * @author lincky
 * @version v1.0.0
 * @time 21:23 2016/12/12
 */
public class SortUtil {

    /**
     * 插入排序<p>
     *
     * 时间复杂度: O(n)~O(n²)，~=O(n²)<p>
     *
     * @param list 需要排序的数组
     */
    public static void insertionSort(List<Integer> list) {
        if (list == null || list.size() == 0) {
            return;
        }
        int size = list.size();
        for (int i = 1; i < size; i++) {
            int key = list.get(i);
            int j = i - 1;
            while (j >= 0 && list.get(j) > key) {
                list.set(j + 1, list.get(j));
                j--;
            }
            list.set(j + 1, key);
        }
    }

    /**
     * 归并排序算法<p>
     * <p>
     * 时间复杂度：O（n*logn）<p>
     * <p>
     * 稳定，但有一定数组开销<p>
     *
     * @param list 需要排序的数组
     * @param low  数组起始索引
     * @param high 数组末尾索引
     */
    public static void mergeSort(List<Integer> list, int low,
                                 int high) {
        if (low < high) {
            int off = (low + high) / 2;
            mergeSort(list, low, off);
            mergeSort(list, off + 1, high);
            merge(list, low, high, off);
        }
    }

    private static void merge(List<Integer> list, int low,
                              int high, int off) {
        int size1 = off - low + 1,
                size2 = high - off;
        List<Integer> list1 = new ArrayList<>(),
                list2 = new ArrayList<>();
        int i1, i2;
        for (i1 = 0; i1 < size1; i1++) {
            list1.add(i1, list.get(low + i1));
        }
        for (i2 = 0; i2 < size2; i2++) {
            list2.add(i2, list.get(off + i2 + 1));
        }
        list1.add(i1, Integer.MAX_VALUE);
        list2.add(i2, Integer.MAX_VALUE);
        i1 = i2 = 0;
        for (int k = low; k <= high; k++) {
            if (list1.get(i1) <= list2.get(i2)) {
                list.set(k, list1.get(i1));
                i1++;
            } else {
                list.set(k, list2.get(i2));
                i2++;
            }
        }
    }


    /**
     * 是否按升序排列 <p>
     *
     * @param list 数组
     * @return <tt>true</tt> 如果数组按升序排列
     */
    public static boolean isAsc(List<Integer> list) {
        if (list == null || list.size() <= 1) {
            return true;
        }
        int size = list.size() - 1;
        for (int i = 0; i < size; i++) {
            if (list.get(i) > list.get(i + 1)) {
                return false;
            }

        }
        return true;
    }

    /**
     * 是否按降序排列 <p>
     *
     * @param list 数组
     * @return <tt>true</tt> - 如果数组按讲序排列
     */
    public static boolean isDesc(List<Integer> list) {
        if (list == null || list.size() <= 1) {
            return true;
        }
        int size = list.size() - 1;
        for (int i = 0; i < size; i++) {
            if (list.get(i) < list.get(i + 1)) {
                return false;
            }
        }
        return true;
    }

    public static boolean isSorted(List<Integer> list) {
        return isAsc(list) || isDesc(list);
    }

    public static boolean isSorted(Integer[] array) {
        List<Integer> list = Arrays.asList(array);
        return isSorted(list);
    }

    private static int leftIndex(int index) {
        return (index << 1) + 1;
    }

    private static int rightIndex(int index) {
        return (index << 1) + 2;
    }

    private static int parentIndex(int index) {
        return (index - 1) >> 1;
    }

    private static void swap(List<Integer> list, int indexA, int indexB) {
        int temp = list.get(indexA);
        list.set(indexA, list.get(indexB));
        list.set(indexB, temp);
    }

    /**
     * 将一个节点构建成最大堆 <p>
     *
     * @param list 数组
     * @param heapSize 堆大小
     * @param index 索引
     */
    private static void maxHeapify(List<Integer> list, int heapSize, int index) {
        int leftIndex = leftIndex(index);
        int rightIndex = rightIndex(index);
        int largestIndex = index;
        if (leftIndex < heapSize &&
                list.get(leftIndex) > list.get(index)) {
            largestIndex = leftIndex;
        }
        if (rightIndex < heapSize &&
                list.get(rightIndex) > list.get(largestIndex)) {
            largestIndex = rightIndex;
        }
        if (largestIndex != index) {
            swap(list, index, largestIndex);
            maxHeapify(list, heapSize, largestIndex);
        }
    }

    /**
     * 构建最大堆 <p>
     *
     * @param list 数组
     */
    private static void buildMaxHeap(List<Integer> list) {
        for (int i = ((list.size() - 1) >> 1); i >= 0; i--) {
            maxHeapify(list, list.size(), i);
        }
    }

    /**
     * 堆排算法 <p>
     *
     * 时间复杂度：O(n*lgn) <p>
     *
     * @param list 数组
     */
    public static void heapSort(List<Integer> list) {
        buildMaxHeap(list);
        for (int i = list.size() - 1; i >= 1; i--) {
            swap(list, 0, i);
            maxHeapify(list, i - 1, 0);
        }
    }

    private static Integer heapMaximun(List<Integer> heap) {
        return heap.get(0);
    }

    private static Integer heapExtractMax(List<Integer> heap,
                                          int heapSize) {
        heap.set(0, heap.get(heap.size() - 1));
        maxHeapify(heap, heapSize - 1, 0);
        heap.remove(heap.size() - 1);
        return heap.get(0);
    }

    @Deprecated
    public static void increaseKey(List<Integer> heap,
                                   int key,
                                   int index) {
        heap.set(index, key);
        int parentIndex = parentIndex(index);
        while (index > 0 &&
                heap.get(parentIndex) < heap.get(index)) {
            swap(heap, parentIndex, index);
            index = parentIndex;
        }
    }

    /**
     * 将数组按主元元素<tt>pivot</tt>排列成三部分区域:小于主元、主元、大于主元 <p>
     *
     * 此方法主元元素索引取末尾索引,即<tt>high</tt>参数的值 <p>
     *
     * @param list 数组
     * @param low 起始索引
     * @param high 末尾索引
     * @return 主元索引
     */
    private static int partition(List<Integer> list,
                                 int low,
                                 int high) {
        int pivot = list.get(high);
        int left = low - 1;
        for (int right = low; right <= high - 1; right++) {
            if (list.get(right) <= pivot) {
                left++;
                if (left != right) {
                    swap(list, left, right);
                }
            }
        }
        // pivot index
        left++;
        if (left != high) {
            swap(list, left, high);
        }
        return left;
    }

    /**
     * 将数组按主元元素<tt>pivot</tt>排列成三部分区域:小于主元、主元、大于主元 <p>
     *
     * 此方法主元元素索引取末尾索引,即<tt>high</tt>参数的值 <p>
     *
     * @param list 数组
     * @param low 起始索引
     * @param high 末尾索引
     * @return 主元索引
     */
    public static quickIndex threePartition(List<Integer> list,
                                 int low,
                                 int high) {
        // 主元元素随机化
        int pivotRandomIndex = RandomUtil.getRandom(low, high);
        int pivot = list.get(pivotRandomIndex);
        int left = low;
        int right = high;
        int equalCount = -1;
        // 将数组划分为三个区域
        while (true) {
            int rightData = list.get(right);
            int leftData = list.get(left);
            if (rightData > pivot) {
                right--;
            } else if (leftData < pivot) {
                left++;
            } else if(leftData == pivot) {
                left++;
                equalCount++;
            } else if (rightData == pivot) {
                right--;
                equalCount++;
            }
            if (left < right) {
                swap(list, left, right);
            } else {
                return new quickIndex(left + 1, left + 1 + equalCount);
            }
        }
    }

    /**
     * 快排 <p>
     *
     * 时间复杂度：O(n*lgn)~O(n²)，~=O(n*lgn) <p>
     *
     * 快速排序复杂度又数组数据结构决定，按主元划分数组时，划分得越平均，
     * 速度越快，反之则越慢 <p>
     *
     * @param list 数组
     * @param low 起始索引
     * @param high 末尾索引
     */
    public static void quickSort(List<Integer> list,
                                 int low,
                                 int high) {
        if (low < high) {
            int off = partition(list, low, high);
            quickSort(list, low, off - 1);
            quickSort(list, off + 1, high);
        }
    }

    public static void quickSort(List<Integer> list) {
        quickSort(list, 0, list.size() - 1);
    }

    /**
     * 随机划分 <p>
     *
     * 将数组按主元元素<tt>pivot</tt>排列成三部分区域:小于主元、主元、大于主元 <p>
     *
     * 此方法主元元素索引取末尾索引,即<tt>high</tt>参数的值 <p>
     *
     * @param list 数组
     * @param low 起始索引
     * @param high 末尾索引
     * @return 主元索引
     */
    private static int randomPartition(List<Integer> list,
                                       int low,
                                       int high) {
        swap(list, high, RandomUtil.getRandom(low, high));
        return partition(list, low, high);
    }

    /**
     * 随机快排 <p>
     *
     * 时间复杂度：O(n*lgn)~O(n²)，~=O(n*lgn) <p>
     *
     * 随机快排中，主元元素随机取值，更加平均稳定 <p>
     *
     * @param list 数组
     *
     */
    public static void randomQuickSort(List<Integer> list) {
        randomQuickSort(list, 0, list.size() - 1);
    }

    /**
     * 随机快排 <p>
     *
     * 时间复杂度：O(n*lgn)~O(n²)，~=O(n*lgn) <p>
     *
     * 随机快排中，主元元素随机取值，更加平均稳定 <p>
     *
     * @param list 数组
     * @param low 起始索引
     * @param high 末尾索引
     */
    public static void randomQuickSort(List<Integer> list,
                                 int low,
                                 int high) {
        if (low < high) {
            int off = randomPartition(list, low, high);
            randomQuickSort(list, low, off - 1);
            randomQuickSort(list, off + 1, high);
        }
    }



    public static class quickIndex {
        int pivotLow;
        int pivotHigh;

        public quickIndex(int pivotLow, int pivotHigh) {
            this.pivotLow = pivotLow;
            this.pivotHigh = pivotHigh;
        }

        @Override
        public String toString() {
            return "quickIndex{" +
                    "pivotLow=" + pivotLow +
                    ", pivotHigh=" + pivotHigh +
                    '}';
        }
    }

    static class SelectResult {
        int value;
        int index;

        SelectResult(int value, int index) {
            this.value = value;
            this.index = index;
        }

        @Override
        public String toString() {
            return "SelectResult{" +
                    "value=" + value +
                    ", index=" + index +
                    '}';
        }
    }


    /**
     * 随机选择算法 <p>
     *
     * 时间复杂度：O(n*lgn)~O(n)，~=O(n*lgn) <p>
     *
     * @param list 数组
     * @param rank 第<tt>rank</tt>小
     * @return 第rank小的索引与数据的封装结果<tt>SelectResult</tt>
     */
    public static SelectResult randomSelect(List<Integer> list,
                                            int rank) {
        return randomSelect(list, 0, list.size() - 1, rank);
    }

    /**
     * 随机选择算法 <p>
     *
     * 时间复杂度：O(n*lgn)~O(n)，~=O(n*lgn) <p>
     *
     * @param list 数组
     * @param low 起始索引
     * @param high 终止索引
     * @param rank 第<tt>rank</tt>小
     * @return 第rank小的索引与数据的封装结果<tt>SelectResult</tt>
     */
    public static SelectResult randomSelect(List<Integer> list,
                                            int low,
                                            int high,
                                            int rank) {
        if (low == high) {
            return new SelectResult(list.get(low), low);
        }
        int off = randomPartition(list, low, high);
        int leftLength = off - low + 1;
        if (rank == leftLength) {
            return new SelectResult(list.get(off), off);
        } else if (rank < leftLength) {
            return randomSelect(list, low, off - 1, rank);
        } else {
            return randomSelect(list, off + 1, high, rank - leftLength);
        }
    }

}